package com.wrial.kind.design;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 最近最少访问Cache
 * put：
 * 1.map not contain deque not full   map.put  deque.add
 * 2.map not contain but deque full  map.remove（deque.removeLast）  map.put  deque.add
 * 3.map contain deque.remove(key) deque.addFitst
 *
 * get:
 * 1.map！contain  return -1
 * 2.map contain   deque.remove(key)  deque.addFirst   return map.get(key)
 */
class LRUCache {

    Map<Integer, Integer> map = new HashMap<>();
    Deque<Integer> deque = new LinkedList();
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        deque.remove(key);
        deque.addFirst(key);
        return map.get(key);
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
           if (deque.size()==capacity){
               map.remove(deque.removeLast());
           }
        } else {
            deque.remove(key);
            map.remove(key);
        }
        deque.addFirst(key);
        map.put(key, value);
    }
}